#include "stdafx.h"
#include "graph.h"

using std::vector;


int * CGraph::BellmanFord( int u ) {

	int cV = GetCountV();
	int * d = new int[ cV ];


	for ( int i=0; i<cV; ++i ) {

		d[ i ] = INT_MAX / 2;
	}
	
	d[ u ] = 0;

	for( int i=0; i<cV-1; ++i ) {
	
		for( int j=0; j<cV; ++j ) {
		
			vector< int > neighbour = GetNeighbours( j );
			vector< int >::iterator itr;
			
			for ( itr = neighbour.begin(); itr!=neighbour.end(); ++itr ) {
			
				if( d[ j ] > d[ *itr ] + GetWeight( j, *itr ) ) {
				
					d[ j ] = d[ *itr ] + GetWeight( j, *itr );
				}
			}
		}
	}

	
	return d;
}